/*
 *find the maximum sum from array where they are not adjent
 */
#include <stdio.h>
#include <iostream>
using namespace std;

int cal(int h1,int length,int b[]);
int mycal(int len, int b[]);

int main()
{
    int n[]={1,2,3,-2,5,-1,4};
    int length=sizeof(n)/sizeof(n[0]);
    //printf("%d",cal(-2,length,n));

    printf("%d",mycal(length,n));

    return 0;
}

/*
 *From net
 */
int cal(int h1,int length,int b[])
{
    if (length-h1==1)
        return b[h1];

    if (length-h1==2)
        return (b[h1]>b[h1+1]?b[h1]:b[h1+1]);

    if (length-h1==3)
        return (b[h1]+b[h1+2]>b[h1+1]?b[h1]+b[h1+2]:b[h1+1]);

    if (h1>=0) 
        return b[h1]+(cal(h1+2,length,b)>cal(h1+3,length,b)?cal(h1+2,length,b):cal(h1+3,length,b));
    else
        return (cal(h1+2,length,b)>cal(h1+3,length,b)?cal(h1+2,length,b):cal(h1+3,length,b));
}

/*
 *Written by myself
 */
int mycal(int len, int b[])
{
    if (len==1)
        return b[len-1];

    if (len==2)
        return (b[len-1]>b[len-2]?b[len-1]:b[len-2]);

    if (len>=3)
        return max(mycal(len-2, b)+b[len-1], mycal(len-1, b));

}
